package algocasts;

public class P7_searchIn2DArray {
    // Time:O(n+m) Space:O(1)
    public int[] searchIn2DArray(int[][] matrix, int target) {
        // 判断边界条件
        if (matrix == null || matrix.length == 0 ||
                matrix[0] == null || matrix[0].length == 0)
            return new int[]{-1, -1};
        // 求行列数
        int m = matrix.length, n = matrix[0].length;
        int i = 0, j = n - 1;
        // 从右上角开始搜索
        while (i < m && j >= 0) {
            // 当前指向大于目标值，下方的数都大于目标值，忽略该列
            if (target < matrix[i][j]) --j;
            // 当前指向的数大于目标值，则左边的数都小于该数，忽略这一行
            else if (target > matrix[i][j]) ++i;
            // 相等就直接返回
            else return new int[]{i, j};
        }
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        P7_searchIn2DArray solution = new P7_searchIn2DArray();
        int[][] matrix = {
                {1, 3, 5},
                {2, 4, 6}};
        int[] ints = solution.searchIn2DArray(matrix, 4);
        System.out.println(ints[0] + " " + ints[1]);
    }
}
